import random


class SequentialSearch:
    """
    顺序搜索类，包含了各种顺序搜索算法的实现。
    """

    def linear_search(self, arr, target):
        """
        在列表中执行线性搜索以找到目标元素。

        概念：
        - 线性搜索通过遍历列表中的每个元素并将其与目标元素进行比较来进行搜索。

        属性：
        - 适用于有序和无序列表。
        - 时间复杂度为O(n)，其中n是列表的大小。

        参数：
            arr (list)：待搜索的列表。
            target：要搜索的目标元素。

        返回值：
            int：如果找到目标元素，则返回目标元素的索引；如果未找到目标元素，则返回-1。
        """
        for i in range(len(arr)):
            if arr[i] == target:
                return i
        return -1

    def sentinel_search(self, arr, target):
        """
        在列表中执行哨兵搜索，将目标元素作为哨兵放置在列表末尾。

        概念：
        - 哨兵搜索是线性搜索的优化，其中将目标元素作为哨兵放置在列表末尾。
        - 这样可以避免在搜索过程中检查边界条件，从而稍微提高性能。

        属性：
        - 适用于有序和无序列表。
        - 时间复杂度为O(n)，其中n是列表的大小。

        参数：
            arr (list)：待搜索的列表。
            target：要搜索的目标元素。

        返回值：
            int：如果找到目标元素，则返回目标元素的索引；如果未找到目标元素，则返回-1。
        """
        last_element = arr[-1]
        arr[-1] = target

        i = 0
        while arr[i] != target:
            i += 1

        arr[-1] = last_element

        if i < len(arr) - 1 or target == arr[-1]:
            return i
        return -1

    def adaptive_search(self, arr, target):
        """
        在列表中执行自适应搜索，根据数据分布动态调整搜索顺序。

        概念：
        - 自适应搜索根据元素的分布情况优化搜索顺序。
        - 当目标元素不存在时，它通过提前终止搜索来减少不必要的比较。

        属性：
        - 适用于有序和无序列表。
        - 最坏情况下的时间复杂度为O(n)，其中n是列表的大小。

        参数：
            arr (list)：待搜索的列表。
            target：要搜索的目标元素。

        返回值：
            int：如果找到目标元素，则返回目标元素的索引；如果未找到目标元素，则返回-1。
        """
        for i in range(len(arr)):
            if arr[i] == target:
                return i

            if arr[i] > target:
                return -1

        return -1

    def balanced_search(self, arr, target, block_size):
        """
        在有序列表中执行平衡顺序搜索，使用基于块的方法。

        概念：
        - 平衡搜索将列表划分为块，并在每个块上执行顺序搜索。
        - 它通过缩小搜索范围来减少比较的次数。

        属性：
        - 仅适用于有序列表。
        - 时间复杂度为O(sqrt(n))，其中n是列表的大小。

        参数：
            arr (list)：待搜索的有序列表。
            target：要搜索的目标元素。
            block_size (int)：每个块的大小。

        返回值：
            int：如果找到目标元素，则返回目标元素的索引；如果未找到目标元素，则返回-1。
        """
        num_blocks = len(arr) // block_size

        for i in range(num_blocks):
            block_start = i * block_size
            block_end = block_start + block_size

            if arr[block_start] <= target <= arr[block_end - 1]:
                for j in range(block_start, block_end):
                    if arr[j] == target:
                        return j
                return -1

        remaining_elements = len(arr) % block_size
        last_block_start = len(arr) - remaining_elements

        if arr[last_block_start] <= target <= arr[-1]:
            for j in range(last_block_start, len(arr)):
                if arr[j] == target:
                    return j

        return -1

    def jump_search(self, arr, target, jump_size):
        """
        在有序列表中执行跳跃搜索，以固定步长进行跳跃。

        概念：
        - 跳跃搜索以固定步长进行跳跃，缩小搜索范围。
        - 它是线性搜索的优化，减少了比较的次数。

        属性：
        - 仅适用于有序列表。
        - 时间复杂度为O(sqrt(n))，其中n是列表的大小。

        参数：
            arr (list)：待搜索的有序列表。
            target：要搜索的目标元素。
            jump_size (int)：跳跃的步长。

        返回值：
            int：如果找到目标元素，则返回目标元素的索引；如果未找到目标元素，则返回-1。
        """
        n = len(arr)
        step = int(jump_size ** 0.5)
        prev = 0

        # 进行跳跃，直到当前步长位置的值大于目标值
        while arr[min(step, n) - 1] < target:
            prev = step
            step += int(jump_size ** 0.5)
            if prev >= n:
                return -1

        # 在当前块内执行线性搜索
        while arr[prev] < target:
            prev += 1

            # 如果到达块的末尾或者超过了列表的大小，则未找到目标元素
            if prev == min(step, n):
                return -1

        if arr[prev] == target:
            return prev

        return -1

    def interpolation_search(self, arr, target):
        """
        在有序列表中执行插值搜索，使用插值估算目标位置。

        概念：
        - 插值搜索通过使用插值估算目标元素的位置。
        - 它适应非均匀分布的数据，减少搜索范围。

        属性：
        - 仅适用于有序列表且元素均匀分布。
        - 时间复杂度为O(log(log(n)))，其中n是列表的大小。

        参数：
            arr (list)：待搜索的有序列表。
            target：要搜索的目标元素。

        返回值：
            int：如果找到目标元素，则返回目标元素的索引；如果未找到目标元素，则返回-1。
        """
        low, high = 0, len(arr) - 1

        # 进行插值搜索，直到找到目标元素或搜索范围耗尽
        while low <= high and arr[low] <= target <= arr[high]:
            # 使用插值估算目标位置
            pos = low + ((target - arr[low]) * (high - low)) // (arr[high] - arr[low])

            if arr[pos] == target:
                return pos

            if arr[pos] < target:
                low = pos + 1
            else:
                high = pos - 1

        return -1


# 使用示例
if __name__ == "__main__":
    # 生成一个随机列表
    my_list = random.sample(range(1, 100), 10)
    my_list.sort()  # 对列表进行排序
    print("列表:", my_list)

    # 生成一个随机目标元素
    target_element = random.choice(my_list)
    print("目标元素:", target_element)

    search_obj = SequentialSearch()

    # 线性搜索
    result = search_obj.linear_search(my_list, target_element)
    print("线性搜索结果:", result)

    # 哨兵搜索
    result = search_obj.sentinel_search(my_list, target_element)
    print("哨兵搜索结果:", result)

    # 自适应搜索
    result = search_obj.adaptive_search(my_list, target_element)
    print("自适应搜索结果:", result)

    # 平衡顺序搜索
    block_size = 2
    result = search_obj.balanced_search(my_list, target_element, block_size)
    print("平衡顺序搜索结果:", result)

    # 跳跃搜索
    jump_size = 2
    result = search_obj.jump_search(my_list, target_element, jump_size)
    print("跳跃搜索结果:", result)

    # 插值搜索
    result = search_obj.interpolation_search(my_list, target_element)
    print("插值搜索结果:", result)
